/*
 * Copyright 2016 Scalified <http://www.scalified.com>
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
//package com.scalified.tree.multinode;
package com.gitee.wsl.struct.tree.multinode

import com.gitee.wsl.ext.base.ArrayExt.arraycopy
import com.gitee.wsl.struct.tree.CategoryTreeNode
import com.gitee.wsl.struct.tree.TreeNode
import com.gitee.wsl.struct.tree.TreeNodeManager.areAllNulls
import com.gitee.wsl.struct.tree.TreeNodeManager.linkParent
import com.gitee.wsl.struct.tree.TreeNodeManager.unlinkParent
import kotlin.math.max


/**
 * Implementation of the K-ary (multi node) tree data structure,
 * based on the resizable array representation
 *
 * @author shell
 * @version 1.0.0
 * @since 1.0.0
 */
class ArrayMultiTreeNode<T:Any> : MultiTreeNode{
    /**
     * Array, which holds the references to the current tree node subtrees
     */
    private var subtrees: Array<TreeNode?>

    /**
     * Number of subtrees currently present in the current tree node
     */
    private var subtreesSize = 0

    /**
     * Current branching factor of the current tree node
     */
    private val branchingFactor: Int

    /**
     * Constructs the [ArrayMultiTreeNode] instance
     *
     * @param data data to store in the current tree node
     */
    constructor(data: T) : super(data) {
        branchingFactor = DEFAULT_BRANCHING_FACTOR
        subtrees = arrayOfNulls(branchingFactor)
    }

    /**
     * Constructs the [ArrayMultiTreeNode] instance
     *
     * @param data data to store in the current tree node
     * @param branchingFactor initial branching factor, that is the number
     * of subtrees the current tree node can have
     * before getting resized
     */
    constructor(data: T, branchingFactor: Int) : super(data) {
        require(branchingFactor >= 0) { "Branching factor can not be negative" }
        this.branchingFactor = branchingFactor
        subtrees = arrayOfNulls(branchingFactor)
    }

    /**
     * Returns the collection of the child nodes of the current node
     * with all of its proper descendants, if any
     *
     *
     * Returns [Collections.emptySet] if the current node is leaf
     *
     * @return collection of the child nodes of the current node with
     * all of its proper descendants, if any;
     * [Collections.emptySet] if the current node is leaf
     */
    override fun subtrees(): List<TreeNode> {
        if (isLeaf) {
            return emptyList()
        }
        val subtrees = ArrayList<TreeNode>(subtreesSize)
        for (i in 0 until subtreesSize) {
            val subtree = this.subtrees[i] as TreeNode
            subtrees.add(subtree)
        }
        return subtrees
    }

    /**
     * Adds the subtree with all of its descendants to the current tree node
     *
     *
     * `null` subtree cannot be added, in this case return result will
     * be `false`
     *
     *
     * Checks whether this tree node was changed as a result of the call
     *
     * @param subtree subtree to add to the current tree node
     * @return `true` if this tree node was changed as a
     * result of the call; `false` otherwise
     */
     override fun add(subtree: TreeNode): Boolean {
        linkParent(subtree, this as CategoryTreeNode)
        ensureSubtreesCapacity(subtreesSize + 1)
        subtrees[subtreesSize++] = subtree
        return true
    }

    /**
     * Increases the capacity of the subtrees array, if necessary, to
     * ensure that it can hold at least the number of subtrees specified
     * by the minimum subtrees capacity argument
     *
     * @param minSubtreesCapacity the desired minimum subtrees capacity
     */
    private fun ensureSubtreesCapacity(minSubtreesCapacity: Int) {
        if (minSubtreesCapacity > subtrees.size) {
            increaseSubtreesCapacity(minSubtreesCapacity)
        }
    }

    /**
     * Increases the subtrees array capacity to ensure that it can hold
     * at least the number of elements specified by the minimum subtrees
     * capacity argument
     *
     * @param minSubtreesCapacity the desired minimum subtrees capacity
     */
    private fun increaseSubtreesCapacity(minSubtreesCapacity: Int) {
        val oldSubtreesCapacity = subtrees.size
        var newSubtreesCapacity = oldSubtreesCapacity + (oldSubtreesCapacity shr 1)
        if (newSubtreesCapacity < minSubtreesCapacity) {
            newSubtreesCapacity = minSubtreesCapacity
        }
        if (newSubtreesCapacity > MAX_ARRAY_SIZE) {
            if (minSubtreesCapacity < 0) {
                throw RuntimeException("OutOfMemoryError")
            }
            newSubtreesCapacity = if (minSubtreesCapacity > MAX_ARRAY_SIZE) Int.MAX_VALUE else MAX_ARRAY_SIZE
        }
        subtrees = subtrees.copyOf(newSubtreesCapacity)
    }

    /**
     * Drops the first occurrence of the specified subtree from the current
     * tree node
     *
     *
     * Checks whether the current tree node was changed as a result of
     * the call
     *
     * @param subtree subtree to drop from the current tree node
     * @return `true` if the current tree node was changed as a result
     * of the call; `false` otherwise
     */
    override fun dropSubtree(subtree: TreeNode): Boolean {
        if ( isLeaf || subtree.isRoot) {
            return false
        }
        val mSubtreeIndex = indexOf(subtree)
        if (mSubtreeIndex < 0) {
            return false
        }
        val mNumShift = subtreesSize - mSubtreeIndex - 1
        if (mNumShift > 0) {
            arraycopy(subtrees, mSubtreeIndex + 1, subtrees, mSubtreeIndex, mNumShift)
        }
        subtrees[--subtreesSize] = null
        unlinkParent(subtree)
        return true
    }

    /**
     * Returns the index of the first occurrence of the specified subtree
     * within subtrees array; `-1` if the subtrees array does not contain
     * such subtree
     *
     * @param subtree subtree to find the index of
     * @return index of the first occurrence of the specified subtree within
     * subtrees array; `-1` if the subtrees array does not contain
     * such subtree
     */
    private fun indexOf(subtree: TreeNode): Int {
        for (i in 0 until subtreesSize) {
            val mSubtree = subtrees[i] as TreeNode
            if (mSubtree == subtree) {
                return i
            }
        }
        return -1
    }

    /**
     * Removes all the subtrees with all of its descendants from the current
     * tree node
     */
    override fun clear() {
        if (!isLeaf) {
            for (i in 0 until subtreesSize) {
                val subtree = subtrees[i] as TreeNode
                unlinkParent(subtree)
            }
            subtrees = arrayOfNulls(branchingFactor)
            subtreesSize = 0
        }
    }

    /**
     * Checks whether the current tree node is a leaf, e.g. does not have any
     * subtrees
     *
     *
     * Overridden to have a faster array implementation
     *
     * @return `true` if the current tree node is a leaf, e.g. does not
     * have any subtrees; `false` otherwise
     */
    override val isLeaf: Boolean
        get() = subtreesSize == 0

    /**
     * Checks whether among the current tree node subtrees there is
     * a specified subtree
     *
     *
     * Overridden to have a faster array implementation
     *
     * @param subtree subtree whose presence within the current tree
     * node children is to be checked
     * @return `true` if among the current tree node subtrees
     * there is a specified subtree; `false` otherwise
     */
    override fun hasSubtree(subtree: TreeNode): Boolean {
        if (isLeaf || subtree.isRoot) {
            return false
        }
        for (i in 0 until subtreesSize) {
            val mSubtree = subtrees[i] as TreeNode
            if (subtree == mSubtree) {
                return true
            }
        }
        return false
    }

    /**
     * Checks whether the current tree node with all of its descendants
     * (entire tree) contains the specified node
     *
     *
     * Overridden to have a faster array implementation
     *
     * @param node node whose presence within the current tree node with
     * all of its descendants (entire tree) is to be checked
     * @return `true` if the current node with all of its descendants
     * (entire tree) contains the specified node; `false`
     * otherwise
     */
    override operator fun contains(node: TreeNode): Boolean {
        if ( isLeaf || node.isRoot) {
            return false
        }
        for (i in 0 until subtreesSize) {
            val subtree = subtrees[i] as TreeNode
            if (subtree == node) {
                return true
            }
            if (subtree.contains(node)) {
                return true
            }
        }
        return false
    }

    /**
     * Removes the first occurrence of the specified node from the entire tree,
     * starting from the current tree node and traversing in a pre order manner
     *
     *
     * Checks whether the current tree node was changed as a result of the call
     *
     *
     * Overridden to have a faster array implementation
     *
     * @param node node to remove from the entire tree
     * @return `true` if the current tree node was changed as a result of
     * the call; `false` otherwise
     */
    override fun remove(node: TreeNode): Boolean {
        if ( isLeaf || node.isRoot) {
            return false
        }
        if (dropSubtree(node)) {
            return true
        }
        for (i in 0 until subtreesSize) {
            val subtree = subtrees[i] as TreeNode
            if (subtree.remove(node)) {
                return true
            }
        }
        return false
    }

    /**
     * Traverses the tree in a pre ordered manner starting from the
     * current tree node and performs the traversal action on each
     * traversed tree node
     *
     *
     * Overridden to have a faster array implementation
     *
     * @param action action, which is to be performed on each tree
     * node, while traversing the tree
     */
     /*fun traversePreOrder(action: TraversalAction<TreeNode>) {
        if (!action.isCompleted) {
            action.perform(this)
            if (!isLeaf) {
                for (i in 0 until subtreesSize) {
                    val subtree = subtrees[i] as TreeNode
                    subtree!!.traversePreOrder(action)
                }
            }
        }
    }*/

    /**
     * Traverses the tree in a post ordered manner starting from the
     * current tree node and performs the traversal action on each
     * traversed tree node
     *
     *
     * Overridden to have a faster array implementation
     *
     * @param action action, which is to be performed on each tree
     * node, while traversing the tree
     */
    /*fun traversePostOrder(action: TraversalAction<TreeNode>) {
        if (!action.isCompleted) {
            if (!isLeaf) {
                for (i in 0 until subtreesSize) {
                    val subtree = subtrees[i] as TreeNode
                    subtree!!.traversePostOrder(action)
                }
            }
            action.perform(this)
        }
    }*/

    /**
     * Returns the height of the current tree node, e.g. the number of edges
     * on the longest downward path between that node and a leaf
     *
     *
     * Overridden to have a faster array implementation
     *
     * @return height of the current tree node, e.g. the number of edges
     * on the longest downward path between that node and a leaf
     */
    override fun height(): Int {
        if (isLeaf) {
            return 0
        }
        var height = 0
        for (i in 0 until subtreesSize) {
            val subtree = subtrees[i] as TreeNode
            height = max(height, subtree.height())
        }
        return height + 1
    }

    /**
     * Adds the collection of the subtrees with all of theirs descendants
     * to the current tree node
     *
     *
     * Checks whether this tree node was changed as a result of the call
     *
     * @param subtrees collection of the subtrees with all of their
     * descendants
     * @return `true` if this tree node was changed as a
     * result of the call; `false` otherwise
     */
    override fun addSubtrees(subtrees: List<TreeNode>): Boolean {
        if (areAllNulls(subtrees)) {
            return false
        }
        for (subtree in subtrees) {
            linkParent(subtree, this as CategoryTreeNode)
        }
        val subtreesArray:Array<TreeNode?> = subtrees.toTypedArray()
        val subtreesArrayLength = subtreesArray.size
        ensureSubtreesCapacity(subtreesSize + subtreesArrayLength)
        arraycopy(subtreesArray, 0, this.subtrees, subtreesSize, subtreesArrayLength)
        subtreesSize += subtreesArrayLength
        return subtreesArrayLength != 0
    }

    /**
     * Returns the collection of nodes, which have the same parent
     * as the current node; [Collections.emptyList] if the current
     * tree node is root or if the current tree node has no subtrees
     *
     *
     * Overridden to have a faster array implementation
     *
     * @return collection of nodes, which have the same parent as
     * the current node; [Collections.emptyList] if the
     * current tree node is root or if the current tree node has
     * no subtrees
     */
    /*
    @SuppressWarnings("unchecked")
    @Override
    public Collection<TreeNode> siblings() {
        if (isRoot()) {
            String message = String.format("Unable to find the siblings. The tree node %1$s is root", root());
            throw new TreeNodeException(message);
        }
        TreeNode mParent =  parent;
        int parentSubtreesSize = mParent.subtreesSize;
        if (parentSubtreesSize == 1) {
            return Collections.emptySet();
        }
        Object[] parentSubtreeObjects = mParent.subtrees;
        Collection<ArrayMultiTreeNode> siblings = new LinkedHashSet<>(parentSubtreesSize - 1);
        for (int i = 0; i < parentSubtreesSize; i++) {
            ArrayMultiTreeNode parentSubtree = (ArrayMultiTreeNode) parentSubtreeObjects[i];
            if (!parentSubtree.equals(this)) {
                siblings.add(parentSubtree);
            }
        }
        return siblings;
    }*/
    companion object {

        /**
         * Default initial branching factor, that is the number of subtrees
         * this node can have before getting resized
         */
        private const val DEFAULT_BRANCHING_FACTOR = 10

        /**
         * The maximum size of array to allocate.
         * Some VMs reserve some header words in an array.
         * Attempts to allocate larger arrays may mResult in
         * OutOfMemoryError: Requested array size exceeds VM limit
         */
        private const val MAX_ARRAY_SIZE = Int.MAX_VALUE - 8
    }
}